#include<iostream>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

typedef struct node {
    char name[20];
    double x;
    double y;
}city;

static const int N = 30;//城市数量
static city citys[N];//城市列表
static double dic[N][N];//各城市之间距离
static bool visit[N];//城市是否访问过
static int seq[N];//局部最优解记录的城市序列
static double answer;//局部最优解

double dic_two_point(city a, city b) {//根据给定两个城市的经纬度计算两城市间实际距离
    //    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    const double PI = 3.1415926535898;
    double radLng1 = a.x * PI / 180.0;
    double radLng2 = b.x * PI / 180.0;
    double as = radLng1 - radLng2;
    double bs = (a.y-b.y) * PI / 180.0;
    double s = 2 * asin(sqrt(pow(sin(as/2), 2) + cos(radLng1) * cos(radLng2) * pow(sin(bs/2), 2)))* 6378.137;
    s =s * 10000 / 10000;
    return s;
}

void set_dic() {//计算各城市之间距离
    for (int i = 0; i<N; ++i) {
        for (int j = 0; j<N; ++j) {
            dic[i][j] = dic_two_point(citys[i], citys[j]);
        }
    }
}

double sum_dic(int* conf) {//计算路径总长度
    double temp = 0;
    for(int i = 1; i<N; ++i){
    temp += dic_two_point(citys[conf[i]], citys[conf[i - 1]]);
    }
    temp += dic_two_point(citys[conf[0]], citys[conf[N - 1]]);
    return temp;
}

void greedy(int start) {//贪心算法实现
    memset(visit, false, sizeof(visit));
    seq[0] = start;
    visit[start] = true;
    int mini = -1;
    int ans = 1e9;
    for (int i = 1; i < N; ++i) {//第i位应该经过的点
        ans = 1e9;
        mini = -1;
        for (int j = 0; j < N; ++j) {
            if (!visit[j] && ans > dic[seq[i - 1]][j]) {
                ans = dic[seq[i - 1]][j];
                mini = j;
            }
        }
        seq[i] = mini;
        visit[mini] = true;
    }
    answer=sum_dic(seq);
}
void input() {//读取城市经纬度数据
    ifstream ifile("ChinaCitys.txt");
    if (!ifile) {
        cout << "open field\n";
        return;
    }
    for(int i = 0; i < N; i++){
        ifile >> citys[i].name >> citys[i].x >> citys[i].y;
    }
}

void output() {//输出局部贪心最优解结果
    cout << "In this time, the best length is " << answer << ", the best road is : \n";
    for (int i = 0; i < N; ++i) {
        cout << citys[seq[i]].name<< " -> ";
    }
    cout << citys[seq[0]].name << endl;
}

int main(){
    clock_t start,finish;
    start=clock();
    input();//使用文件读取数据初始化城市经纬度
    set_dic();
    double best = DBL_MAX;
    for(int i = 0; i < N; i++) {//依次从每个城市作为起始
        greedy(i);
        output();
        if(best > answer){
            best = answer;
        }
    }
    cout << "The current best length of the road is " << best << "km.\n";
    finish=clock();
    cout << "The run time is " << (double)(finish-start) * 1000 / CLOCKS_PER_SEC << "ms.\n";
    return 0;
}
